//
// Created by Snow on 2023/4/2.
//
//二叉树的构造
//先序序列和中序序列唯一构造二叉树
#include<cstdio>
#include <cstdlib>
#define MaxSize 50
typedef char ElemType;
typedef struct node
{
    ElemType data;//数据元素
    struct node *lchild;//指向左孩子结点
    struct node *rchild;//指向右孩子结点
}BTNode;
//销毁二叉树
void DestroyBTree(BTNode *&b)
{
    if(b!=nullptr)
    {
        DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
        free(b);
    }
}
void DispBTree(BTNode *b)
{
    if(b!=nullptr)
    {
        printf("%c",b->data);
        if(b->lchild!=nullptr||b->rchild!=nullptr)
        {
            printf("(");//有孩子结点时才输出"("
            DispBTree(b->lchild);//递归输出左子树
            if(b->rchild!=nullptr)
                printf(",");//有右孩子才输出","
            DispBTree(b->rchild);//递归输出右子树
            printf(")");//有孩子结点时才输出")"
        }
    }
}
BTNode *CreatBT1(char *pre,char *in,int n)
//pre存放先序序列，in存放中序序列，n为二叉树的结点个数，本算法执行后返回构造的二叉链的根结点指针b
{
    BTNode *b;
    char *p;
    int k;
    if(n<=0)return nullptr;
    b=(BTNode*)malloc(sizeof(BTNode));//创建二叉树结点b
    b->data=*pre;
    for(p=in;p<in+n;p++)//在中序序列中找等于*pre字符的位置k
        if(*p==*pre)//pre指向根节点
            break;//在in中找到后退出循环
    k=p-in;//确定根节点在in中的位置
    b->lchild=CreatBT1(pre+1,in,k);//递归构造左子树
    b->rchild=CreatBT1(pre+k+1,p+1,n-k-1);//递归构造有子树
    return b;
}
//中序序列和后续序列构造二叉树
BTNode *CreatBT2(char *post,char *in,int n)
//post存放后序序列，in存放中序序列，n为二叉树的结点个数，本算法执行后返回构造的二叉链的根结点指针b
{
    BTNode *b;
    char r,*p;
    int k;
    if(n<=0)return nullptr;
    r=*(post+n-1);//根节点值
    b=(BTNode*)malloc(sizeof(BTNode));//创建二叉树结点b
    b->data=r;
    for(p=in;p<in+n;p++)//在in中查找根节点
        if(*p==r)break;
    k=p-in;//k为根节点在in中的下标
    b->lchild=CreatBT2(post,in,k);//递归构造左子树
    b->rchild=CreatBT2(post+k,p+1,n-k-1);//递归构造右子树
    return b;
}
//将二叉树的顺序结构转换成二叉链储存结构
typedef ElemType SqBTree[MaxSize];//二叉树顺序储存结构的类型声明
BTNode *trans(SqBTree a,int i)
{
    BTNode *b;
    if(i>MaxSize)
        return nullptr;
    if(a[i]=='#')return nullptr;//空节点返回nullptr
    b=(BTNode*)malloc(sizeof(BTNode));//创建根结点吧
    b->data=a[i];
    b->lchild=trans(a,2*i);//递归创建左子树
    b->rchild=trans(a,2*i+1);//递归创建右子树
    return b;//返回根结点
}
int main()
{
    BTNode *b;
    SqBTree a="0ABCD#EF##G####################";
    b=trans(a,1);
    printf("b:");
    DispBTree(b);
    printf("\n");
    DestroyBTree(b);
    return 0;
}
